package com.leetcode.algorithm.y19.m11;

import java.util.ArrayList;
import java.util.List;

/**
 * 
 * (done)746. 使用最小花费爬楼梯
 * (done)1010. 总持续时间可被 60 整除的歌曲
 * (done)1013. 将数组分成和相等的三个部分
 * (done)1018. 可被 5 整除的二进制前缀
 * (done)1160. 拼写单词
 * 
 * @author jie.deng
 * @time 2019年11月27日 下午8:12:16
 */
public class MySolution1127 {

	/**
	 * (done)746. 使用最小花费爬楼梯
	 * 
	 * 数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。
	 * 
	 * 每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
	 * 
	 * 您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。
	 * 
	 * 示例 1:
	 * 
	 * 输入: cost = [10, 15, 20]
	 * 输出: 15
	 * 解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。
	 *  示例 2:
	 * 
	 * 输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
	 * 输出: 6
	 * 解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。
	 * 注意：
	 * 
	 * cost 的长度将会在 [2, 1000]。
	 * 每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999]。
	 * 
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/min-cost-climbing-stairs
	 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
	 * @param cost
	 * @return
	 */
	public int minCostClimbingStairs(int[] cost) {
		int len = cost.length;
		for (int i = 2; i < len; i++) {
			cost[i] += Math.min(cost[i - 2], cost[i - 1]);
		}
		return Math.min(cost[len - 2], cost[len - 1]);
	}

	/**
	 * (done)1010. 总持续时间可被 60 整除的歌曲
	 * 
	 * 在歌曲列表中，第 i 首歌曲的持续时间为 time[i] 秒。
	 * 
	 * 返回其总持续时间（以秒为单位）可被 60 整除的歌曲对的数量。形式上，我们希望索引的数字  i < j 且有 (time[i] + time[j]) % 60 == 0。
	 * 
	 *  
	 * 
	 * 示例 1：
	 * 
	 * 输入：[30,20,150,100,40]
	 * 输出：3
	 * 解释：这三对的总持续时间可被 60 整数：
	 * (time[0] = 30, time[2] = 150): 总持续时间 180
	 * (time[1] = 20, time[3] = 100): 总持续时间 120
	 * (time[1] = 20, time[4] = 40): 总持续时间 60
	 * 示例 2：
	 * 
	 * 输入：[60,60,60]
	 * 输出：3
	 * 解释：所有三对的总持续时间都是 120，可以被 60 整数。
	 *  
	 * 
	 * 提示：
	 * 
	 * 1 <= time.length <= 60000
	 * 1 <= time[i] <= 500
	 * 
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/pairs-of-songs-with-total-durations-divisible-by-60
	 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
	 * 
	 * @param times
	 * @return
	 */
	public int numPairsDivisibleBy60(int[] times) {
		int[] arr = new int[60];
		for (int i = 0; i < times.length; i++) {
			int remain = times[i] % 60;
			arr[remain] = arr[remain] + 1;
		}
		int sum = 0;
		if (arr[0] >= 2) {
			sum += arr[0] * (arr[0] - 1) / 2;
		}
		if (arr[30] >= 2) {
			sum += arr[30] * (arr[30] - 1) / 2;
		}
		for (int i = 1; i <= 29; i++) {
			sum += arr[i] * arr[60 - i];
		}
		return sum;
	}

	/**
	 * (done)1013. 将数组分成和相等的三个部分
	 * 
	 * 给定一个整数数组 A，只有我们可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。
	 * 
	 * 形式上，如果我们可以找出索引 i+1 < j 且满足 (A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1]) 就可以将数组三等分。
	 * 
	 *  
	 * 
	 * 示例 1：
	 * 
	 * 输出：[0,2,1,-6,6,-7,9,1,2,0,1]
	 * 输出：true
	 * 解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1
	 * 示例 2：
	 * 
	 * 输入：[0,2,1,-6,6,7,9,-1,2,0,1]
	 * 输出：false
	 * 示例 3：
	 * 
	 * 输入：[3,3,6,5,-2,2,5,1,-9,4]
	 * 输出：true
	 * 解释：3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4
	 *  
	 * 
	 * 提示：
	 * 
	 * 3 <= A.length <= 50000
	 * -10000 <= A[i] <= 10000
	 * 
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/partition-array-into-three-parts-with-equal-sum
	 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
	 * @param arr
	 * @return
	 */
	public boolean canThreePartsEqualSum(int[] arr) {
		long sum = 0;
		for (int i = 0; i < arr.length; i++) {
			sum += arr[i];
		}
		if (sum % 3 != 0) {
			return false;
		}
		long target = sum / 3;
		int i = 0;
		int j = arr.length - 1;
		sum = arr[i];
		while (i + 1 < j && sum != target) {
			i++;
			sum += arr[i];
		}
		if (i + 1 < j && sum == target) {
			sum = arr[j];
			while (i + 1 < j && sum != target) {
				j--;
				sum += arr[j];
			}
		}
		return (i + 1 < j && sum == target);
	}

	/**
	 * (done)1018. 可被 5 整除的二进制前缀
	 * 
	 * 给定由若干 0 和 1 组成的数组 A。我们定义 N_i：从 A[0] 到 A[i] 的第 i 个子数组被解释为一个二进制数（从最高有效位到最低有效位）。
	 * 
	 * 返回布尔值列表 answer，只有当 N_i 可以被 5 整除时，答案 answer[i] 为 true，否则为 false。
	 * 
	 *  
	 * 
	 * 示例 1：
	 * 
	 * 输入：[0,1,1]
	 * 输出：[true,false,false]
	 * 解释：
	 * 输入数字为 0, 01, 011；也就是十进制中的 0, 1, 3 。只有第一个数可以被 5 整除，因此 answer[0] 为真。
	 * 示例 2：
	 * 
	 * 输入：[1,1,1]
	 * 输出：[false,false,false]
	 * 示例 3：
	 * 
	 * 输入：[0,1,1,1,1,1]
	 * 输出：[true,false,false,false,true,false]
	 * 示例 4：
	 * 
	 * 输入：[1,1,1,0,1]
	 * 输出：[false,false,false,false,false]
	 *  
	 * 
	 * 提示：
	 * 
	 * 1 <= A.length <= 30000
	 * A[i] 为 0 或 1
	 * 
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/binary-prefix-divisible-by-5
	 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
	 * @param A
	 * @return
	 */
	public List<Boolean> prefixesDivBy5(int[] arr) {
		int len = arr.length;
		List<Boolean> list = new ArrayList<Boolean>(len);
		int num = 0;
		for (int i = 0; i < len; i++) {
			num = (num * 2 + arr[i]) % 5;
			list.add(Boolean.valueOf(num == 0));
		}
		return list;
	}

	/**
	 * (done)1160. 拼写单词
	 * 
	 * 给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。
	 * 
	 * 假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。
	 * 
	 * 注意：每次拼写时，chars 中的每个字母都只能用一次。
	 * 
	 * 返回词汇表 words 中你掌握的所有单词的 长度之和。
	 * 
	 *  
	 * 
	 * 示例 1：
	 * 
	 * 输入：words = ["cat","bt","hat","tree"], chars = "atach"
	 * 输出：6
	 * 解释： 
	 * 可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。
	 * 示例 2：
	 * 
	 * 输入：words = ["hello","world","leetcode"], chars = "welldonehoneyr"
	 * 输出：10
	 * 解释：
	 * 可以形成字符串 "hello" 和 "world"，所以答案是 5 + 5 = 10。
	 *  
	 * 
	 * 提示：
	 * 
	 * 1 <= words.length <= 1000
	 * 1 <= words[i].length, chars.length <= 100
	 * 所有字符串中都仅包含小写英文字母
	 * 
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/find-words-that-can-be-formed-by-characters
	 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
	 * @param words
	 * @param chars
	 * @return
	 */
	public int countCharacters(String[] words, String chars) {
		int retNum = 0;
		// chCntArr用于记录'a'-'z'在字符串chars中出现的次数
		int len = chars.length();
		int[] chCntArr = new int[26];
		for (int i = 0; i < len; i++) {
			chCntArr[chars.charAt(i) - 'a'] += 1;
		}
		for (String str : words) {
			int length = str.length();
			if (length > len) {
				continue;
			}
			if (chars.contains(str)) {
				retNum += length;
				continue;
			}
			int[] arr = new int[26];
			for (int i = 0; i < length; i++) {
				arr[str.charAt(i) - 'a'] += 1;
			}
			boolean flag = true;
			for (int i = 0; i < 26; i++) {
				if (arr[i] > chCntArr[i]) {
					flag = false;
					break;
				}
			}
			retNum += flag ? length : 0;
		}
		return retNum;
	}

}
